package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func hasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}

	sum -= root.Val
	if sum == 0 && (root.Left == nil && root.Right == nil) {
		return true
	}

	if root.Left != nil && hasPathSum(root.Left, sum) {
		return true
	}

	return hasPathSum(root.Right, sum)
}

func levelOrderBottom(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	if root.Left == nil && root.Right == nil {
		return [][]int{[]int{root.Val}}
	}

	rs, level, n := [][]int{}, 0, new(TreeNode)
	q, next := []*TreeNode{root}, make([]*TreeNode, 0, 2)
	i := 0
	for {
		n, i = q[i], i+1
		if len(rs) < level+1 {
			rs = append(rs, []int{n.Val})
		} else {
			rs[level] = append(rs[level], n.Val)
		}

		if n.Left != nil {
			next = append(next, n.Left)
		}
		if n.Right != nil {
			next = append(next, n.Right)
		}

		if i < len(q) {
			continue
		}

		if len(next) == 0 {
			break
		}

		q, next, level, i = next, q[:0], level+1, 0
	}

	for i, length := 0, len(rs); i < length/2; i++ {
		rs[i], rs[length-i-1] = rs[length-i-1], rs[i]
	}
	return rs
}
